/*
 * Copyright (c) 2004-2005 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Kevin Lim
 */

#include "base/intmath.hh"
#include "base/trace.hh"
#include "cpu/edge/pred/ibtb.hh"

DefaultIBTB::DefaultIBTB(unsigned _iExitPredictorEntries, 
        unsigned _numEntries,
        unsigned _iExitLength, 
        unsigned _blockShiftAmt)
    :iExitPredictorEntries(_iExitPredictorEntries),
     numEntries(_numEntries),
     iExitLength(_iExitLength),
     blockShiftAmt(_blockShiftAmt)
{
    DPRINTF(EdgePredUnit,"IBTB: Creating IBTB objects.\n");

    if (!isPowerOf2(numEntries)) {
        fatal("IBTB entries is not a power of 2!");
    }

    if (!isPowerOf2(iExitPredictorEntries)) {
        fatal("IBTB exit predictor entries is not a power of 2!");
    }

    iExitPredictor.resize(iExitPredictorEntries);

    for(unsigned i = 0 ; i < iExitPredictorEntries ; ++i) {
        iExitPredictor[i].iExit = 0;
        iExitPredictor[i].hysteresis = false;
    }

    ibtb.resize(numEntries);

    for(unsigned i = 0 ; i < numEntries ; ++i) {
        ibtb[i].target = 0;
        ibtb[i].hysteresis = false;
    }

    iExitPredictorIdxMask = iExitPredictorEntries - 1;

    idxMask = numEntries - 1;

    iExitMask = (1 << iExitLength) - 1;

    idxLength = floorLog2(numEntries);

    iExitPredictorIdxLength = floorLog2(iExitPredictorEntries);
}

void
DefaultIBTB::reset() 
{
    for(unsigned i = 0 ; i < iExitPredictorEntries ; ++i) {
        iExitPredictor[i].iExit = 0;
        iExitPredictor[i].hysteresis = false;
    }
    
    for(unsigned i = 0 ; i < numEntries ; ++i) {
        ibtb[i].target = 0;
        ibtb[i].hysteresis = false;
    }
}

unsigned
DefaultIBTB::calcIExitPredictorIdx(unsigned index, ExitID exitID) 
{
    unsigned idx = (index ^ (exitID << (iExitPredictorIdxLength - 3))) & iExitPredictorIdxMask;
    return idx;
}

unsigned
DefaultIBTB::calcIBTBIdx(Addr PC, unsigned iExit, ExitID exitID) 
{
    unsigned idx = (PC ^ ((exitID << (idxLength - 3)) | (iExit << (idxLength - 1)))) & idxMask;
    return idx;
}

Addr
DefaultIBTB::targetGen(Addr target, unsigned iExit) 
{
    Addr temp_target = ((target << iExitLength) | iExit ) << blockShiftAmt;
    return temp_target;
}

unsigned
DefaultIBTB::iExitGen(Addr target)
{
    unsigned iExit = (target >> blockShiftAmt) & iExitMask;
    return iExit;
}

Addr
DefaultIBTB::lookup(const Addr &PC, unsigned index, ExitID exitID) 
{
    unsigned iExitPredictorIdx = calcIExitPredictorIdx(index, exitID);
    unsigned predicted_iExit = iExitPredictor[iExitPredictorIdx].iExit;
    unsigned ibtbIdx = calcIBTBIdx(PC,predicted_iExit,exitID);
    Addr tempTarget = ibtb[ibtbIdx].target;
    Addr target = targetGen(tempTarget,predicted_iExit);
    return target;
}

void
DefaultIBTB::update(const Addr &PC, unsigned index, 
        ExitID actual_exit, Addr corr_target) 
{
    //update iExitPredictor table.
    unsigned iExitPredictorIdx = calcIExitPredictorIdx(index, actual_exit);
    unsigned corr_iExit = iExitGen(corr_target); 
    IExitPredictorEntry iExitPredictorEntry= iExitPredictor[iExitPredictorIdx];
    IExitPredictorEntry new_iExitPredictorEntry;
    new_iExitPredictorEntry.iExit = iExitPredictorEntry.hysteresis?
        iExitPredictorEntry.iExit:corr_iExit;
    new_iExitPredictorEntry.hysteresis = (iExitPredictorEntry.iExit == corr_iExit);
    iExitPredictor[iExitPredictorIdx] = new_iExitPredictorEntry;
    //update ibtb table.
    unsigned ibtbIdx =calcIBTBIdx(PC,corr_iExit,actual_exit);
    IBTBEntry ibtbEntry = ibtb[ibtbIdx];
    IBTBEntry new_ibtbEntry;
    Addr target = corr_target >> (blockShiftAmt + iExitLength);
    new_ibtbEntry.target = ibtbEntry.hysteresis ? ibtbEntry.target : target;
    new_ibtbEntry.hysteresis = (ibtbEntry.target == target);
    ibtb[ibtbIdx] = new_ibtbEntry;
}

